<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 找到所有好字符串 -->
    <script>
      let MOD = Math.pow(10, 9) + 7
      var findGoodStrings = function (n, s1, s2, evil) {
        let next = getNext(evil)
        let memo = {}
        let dfs = (i, bound, status) => {
          //status代表evil作为子串左边代表已经匹配好的部分
          if (status === evil.length) return 0
          if (i === s1.length) return 1
          if (memo[[i, bound, status]]) return memo[[i, bound, status]]
          memo[[i, bound, status]] = 0
          let l = (bound & (1 << 0) ? s1[i] : 'a').charCodeAt()
          let r = (bound & (1 << 1) ? s2[i] : 'z').charCodeAt()
          for (let c = l; c <= r; c++) {
            //1、bound更新
            let lBound = bound & (1 << 0) && s1[i].charCodeAt() === c ? 1 << 0 : 0
            let rBound = bound & (1 << 1) && s2[i].charCodeAt() === c ? 1 << 1 : 0
            let nxtBound = lBound | rBound
            //2、status更新
            let char = String.fromCharCode(c)
            let nxtStatus = status //将evil当成子串，找到子串能够匹配的点位
            while (nxtStatus > 0 && evil[nxtStatus] !== char) nxtStatus = next[nxtStatus]
            nxtStatus = evil[nxtStatus] == char ? nxtStatus + 1 : 0
            //3、向下递推
            memo[[i, bound, status]] += dfs(i + 1, nxtBound, nxtStatus)
          }
          memo[[i, bound, status]] %= MOD
          return memo[[i, bound, status]]
        }
        return dfs(0, 3, 0)
      }
      var getNext = function (s) {
        let n = s.length
        let next = [] //状态：代表i左侧的字符串的最长公共前缀的下一个位置
        //边界
        next[0] = -1 //左侧字符串长度为0，如果在该点失配，则
        next[1] = 0 //左侧字符串长度为1，如果在该点失配，则与第一个点比较
        let a = 0
        let b = 1
        while (b < n) {
          //注意最终的next数组长为n+1，因为第n个字符串左侧才是最终next数组的总长
          //1、递推：a = next[a]
          while (a !== -1 && s[a] !== s[b]) {
            a = next[a]
          }
          //2、边界：代表++b的左侧字符串无最长公共前后缀
          if (a === -1) {
            next[++b] = 0
            a = 0
          }
          //3、递推
          else next[++b] = ++a
        }
        return next
      }
      console.log(getNext(2, 'aa', 'da', 'b'))
    </script>
  </body>
</html>
